package q782_movesToChessboard;

public class Solution {
    public int movesToChessboard(int[][] board) {
        int sum = (1 << board.length) - 1;// sum表示的是不同的mask的行之间应该的和
        int move1 = rowMove(board, sum);
        if (move1 == -1) {
            return -1;
        }
        int move2 = colMove(board, sum);
        if (move2 == -1) {
            return -1;
        }
        return move1 + move2;
    }

    int rowMove(int grid[][], int sum) {
        //行调整应该进行的次数
        int count1 = 1, count2 = 0;
        int mask = findRowMask(grid, 0);
        if (Math.abs(Integer.bitCount(mask) - (grid.length >> 1)) > 1) {
            return -1;
        }// 1的数量必须是长度的一半或者加1
        int pos[] = new int[grid.length];
        for (int i = 1; i < grid.length; i++) {
            int m = findRowMask(grid, i);
            if (m == mask) {
                count1++;
            } else if (m == sum - mask) {
                count2++;
                pos[i] = 1;
            } else {
                return -1;
            }
        }
        if (Math.abs(count1 - count2) > 1) {
            return -1;
        }// 交替出现的前提是差别不超过1
        int ans = 0;
        if (count1 == count2) {
            // 行数为偶数，那么只考虑偶数行，数字数量少的那个交换
            for (int i = 0; i < grid.length; i += 2) {
                if (pos[i] == 1) {
                    ans++;
                }
            }
            ans = Math.min(ans, (grid.length >> 1) - ans);
        } else {
            int start = count1 > count2 ? 0 : 1;// 的那个应该在第0行
            for (int i = 0; i < grid.length; i += 2) {
                if (pos[i] != start) {
                    ans++;
                }
            }
        }
        return ans;
    }

    int colMove(int grid[][], int sum) {
        // 列调整应该进行的次数
        int count1 = 1, count2 = 0;
        int mask = findColMask(grid, 0);
        if (Math.abs(Integer.bitCount(mask) - (grid.length >> 1)) > 1) {
            return -1;
        }// 1的数量必须是长度的一半或者加1
        int pos[] = new int[grid.length];
        for (int i = 1; i < grid.length; i++) {
            int m = findColMask(grid, i);
            if (m == mask) {
                count1++;
            } else if (m == sum - mask) {
                count2++;
                pos[i] = 1;
            } else {
                return -1;
            }
        }
        if (Math.abs(count1 - count2) > 1) {
            return -1;
        }// 交替出现的前提是差别不超过1
        int ans = 0;
        if (count1 == count2) {
            // 行数为偶数，那么只考虑偶数列，数字数量少的那个交换
            for (int i = 0; i < grid.length; i += 2) {
                if (pos[i] == 1) {
                    ans++;
                }
            }
            ans = Math.min(ans, (grid.length >> 1) - ans);
        } else {
            int start = count1 > count2 ? 0 : 1;// 多的那个应该在第0列
            for (int i = 0; i < grid.length; i += 2) {
                if (pos[i] != start) {
                    ans++;
                }
            }
        }
        return ans;
    }

    int findRowMask(int grid[][], int row) {
        // 将row行转化为二进制数
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            ans |= grid[row][i] << i;
        }
        return ans;
    }

    int findColMask(int grid[][], int col) {
        // 将col列转化为二进制数
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            ans |= grid[i][col] << i;
        }
        return ans;
    }
}
